package com.leetcode.partition3;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/29 17:54
 */
public class LC221最大正方形 {

    public static int maximalSquare(char[][] matrix) {
        return dynamicProgramming(matrix);
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        System.out.println(maximalSquare(matrix));
    }

    private static int dynamicProgramming(char[][] matrix) {
        int answer = 0;
        //dp[i][j]表示以matrix[i][j]为正方形右下角所能形成的最大正方形的边
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '0') continue;
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return answer * answer;
    }
}
